Use of network data communications for commercial and non-commercial applications continues to grow at an extremely rapid pace. This growth in the use of data communications is a driving factor for the development and implementation of data networks that provide increase bandwidth and reliability.
One approach that is used to provide such high bandwidth data communication and/or reliable data communication services is the use of aggregation groups. An aggregation group is a grouping of paths between two network devices in a data network that collectively provide higher bandwidth and reliability. Each path in the group can be individually used to communicate data between the two network devices and can include a single link that directly connects the two network devices or multiple links that connect the two network devices through other network devices. Depending on the direction of data being communicated between the two network devices, one of the network devices can operate as a data source and the other network device can operate as a data destination. A link in the path can take the form of a physical link or virtual link. Virtual links, as the term indicates, can be implemented by defining a plurality of logical links. The plurality of logical links can then be implemented using one or more physical links.
Aggregation groups can be formed in a number of different ways. For example, a route computation process (RCP) can be used to determine the connectivity in a data network and compute the “least cost paths” between any two network devices in the data network. A commonly used measure of the cost of a path between two network devices in a data network is the total cost of all the individual links in the path or, more simply, the number of links in the path. The least cost paths computed by the RCP can be pushed to a forwarding information base (FIB) in a data source network device. The data source network device can use the FIB to look up a least cost path to forward packets of a data flow from the data source network device to a data destination network device. If multiple least cost paths exist between the two network devices, the RCP can aggregate them into an aggregation group and the data source network device can assign packets of the data flow to one path (or member) within the aggregation group for forwarding to the data destination network device.
Network devices commonly use a mathematical “hash” based scheme to identify and map data flows to a specific path in an aggregation group. A mathematical hash is computed using key packet attributes, such as select fields in various packet headers. The hash value is then further reduced to select a member of the aggregation group. For instance, a hash can be generated by applying an “XOR” or “CRC” (Cyclic Redundancy Check) function to selected packet attributes such as the source address, the destination address, the priority of the packet and/or the protocol identifier. This gives a “hash digest” of a specific size. Then, if the target aggregation group has K members, a (Hash Value modulo K) operation results in a number in the range (0 to K−1) that can be used to select a member of the aggregation group.
A data flow can be defined in a number of ways. For example, a data flow can be defined as packets traversing between a source and a destination device that are associated with an individual application and/or user and which are part of the same communication session. This can be referred to as a micro-flow. Alternatively, a data flow can be defined more indirectly as a flow that includes packets that mathematically hash to the same value at a network device. Such a data flow can be termed a macro-flow. Accordingly, macro-flows can include multiple micro-flows. For purposes of clarity, the term “flow” or “data flow,” as used herein, can refer to any data flow (e.g., micro-flows or macro-flows).
While such hash based approaches can provide for random statistical distribution of flows across members of an aggregation group, such approaches have certain drawbacks. For instance, if there are large differences in the amount of data being communicated in a flow or flows that are assigned to one member of an aggregation group as compared to the amount of data being communicated by a flow or flows that are assigned to another member of the aggregation group, the situation can result in a significant imbalance in the amount of data traffic being communicated by the members of the aggregation group. Such imbalances can result in data congestion and packets being dropped and, therefore, inefficient use of available bandwidth. For instance, one member of an aggregation group can be oversubscribed (e.g., by receiving more data than the member of the aggregation group can transmit in a given time), while other members of the aggregation group are idle or carry very little data traffic.
In addition, all members of an aggregation group can be oversubscribed or can be carrying large amounts of data. In such an instance, no real solution is possible other than the conventional approach of choosing one member from the congested aggregation group to communicate a flow.
The present disclosure will be described with reference to the accompanying drawings. The drawing in which an element first appears is typically indicated by the leftmost digit(s) in the corresponding reference number.